package cn.edu.xjtu.work.lowestCommonAncestor;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

/**
 * 235. 二叉搜索树的最近公共祖先
 * 
 * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
 * 
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x
 * 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 */
public class Solution {
    public static void main(String[] args) {
        Solution solu = new Solution();
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        System.out.println(solu.lowestCommonAncestor(root, root, root.left));
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        int small = p.val;
        int big = q.val;
        // 保证p中保存的是二者中的较小值
        if (p.val > q.val) {
            small = q.val;
            big = p.val;
        }
        while (root != null) {
            if (root.val < small) {
                root = root.right;
            } else if (root.val > big) {
                root = root.left;
            } else {
                return root;
            }
        }
        return null;
    }
}
